package com.zhugang.week13.sorting;

import java.util.Arrays;

/**
 * @program algorithms
 * @description: mergeSort
 * @author: chanzhugang
 * @create: 2022/09/30 23:42
 */
public class MergeSort implements IMutableSorter {

    /**
     * 归并排序
     * O(nlogn)
     *
     * @param A
     */
    @Override
    public void sort(int[] A) {
        mergeSort(A, 0, A.length);
    }

    private void mergeSort(int[] A, int l, int r) {
        if (r - l <= 1) {
            // 递归终止条件
            return;
        }
        int mid = (l + r + 1) / 2;
        // 分治：递归
        mergeSort(A, l, mid);
        mergeSort(A, mid, r);

        // 合并两个有序数组
        merge(A, l, mid, r);
    }

    private void merge(int[] A, int l, int mid, int r) {
        int[] B = Arrays.copyOfRange(A, l, mid + 1);
        int[] C = Arrays.copyOfRange(A, mid, r + 1);
        // 1 3 5 7 100 |  2 4 6 8 100:  添加哨兵，简化编码
        B[B.length - 1] = C[C.length - 1] = Integer.MAX_VALUE;

        // 双指针分别指向两个数组
        int i = 0, j = 0;
        for (int k = l; k < r; k++) {
            if (B[i] < C[j]) {
                A[k] = B[i++];
            } else {
                A[k] = C[j++];
            }
        }
    }
}